package fun.coding.leetcode;

public class UniqueBinarySearchTrees {

	public static void main(String[] args) {
		// http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics
		// This is Catalan number
		UniqueBinarySearchTrees ubst = new UniqueBinarySearchTrees();
		System.out.println(ubst.numTrees(4));
	}

	public int numTrees(int n) {
		if (n <= 1) return 1;
		
		int[] count = new int[n + 1];
		count[0] = 1;
		count[1] = 1;
		
		// Think about partition the tree, left part * right part, and use DP to finish it.
		// C(n+1) = sigma C(i) * C(n-i) i = 0 to n
		for (int i = 2; i <= n; i++) {
			int sum = 0;
			for (int j = 1; j <= i; j++) {
				sum += count[j - 1] * count[i - j];
			}
			count[i] = sum;
		}
		return count[n];
	}
}
